package ljl.alg.wangzheng_camp.round1.find_the_law;

public class _01_05_one_edit {
    
    /**
     * 我发现我从来没有真正理解编辑距离
     * 过一阵再做，还是不会
     *
     * 首先，这道题明明是在考编辑距离，结果他妈的
     * 大家都用的不是编辑距离解法，他妈的！
     *
     * 其次，我打算用编辑距离，结果发现不会写！
     *
     * 再次，抄别人的，写出来了，发现只打败了 5% 的人，我日他妈的！
     * */
    public boolean oneEditAway2(String first, String second) {
        int m = first.length(), n = second.length();
        // [0][0] 恒为 0
        // 我感觉这个 dp 含义是：从 first 的 i 到 second 的 j 需要修改多少次？
        // 如果相等，那就考虑 i - 1, j - 1
        int[][] dp = new int[m + 1][n + 1];
        // 0 到其它长度，是 i
        for (int i = 1; i <= m; i++) {
            dp[i][0] = i;
        }
        for (int i = 1; i <= n; i++) {
            dp[0][i] = i;
        }
    
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                /*
                * 下面这一段不会写，忘了，主要是没有理解 dp 的含义
                * 好装逼，不求甚解！
                * */
                if(first.charAt(i - 1) == second.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                }else {
                    // 不知 i - 1, j 可否理解为添加一个字符，后面那个理解为删除一个字符，最后一个理解为替换一个字符？
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                }
            }
        }
        
        return dp[m][n] < 2;
    }
    
    /**
     * 官方题解
     * 比较清晰，不想解释了
     * */
    public boolean oneEditAway22(String first, String second) {
        int m = first.length(), n = second.length();
        if (m - n == 1) {
            return check1(second, first);
        } else if (n - m == 1) {
            return check1(first, second);
        } else if (m == n) {
            boolean dif = false;
            for (int i = 0; i < m; i++) {
                if (first.charAt(i) != second.charAt(i)) {
                    if (!dif)
                        dif = true;
                    else return false;
                }
            }
            return true;
        }
        return false;
    }
    
    boolean check1(String first, String second) {
        int m = first.length(), n = second.length();
        int i = 0, j = 0;
        while (i < m && j < n) {
            if (first.charAt(i) == second.charAt(j))
                i++;
            j++;
            if (j - i > 1)
                return false;
        }
        return true;
    }
    
    /**
     * 有好事者，贡献了一个解法
     * */
    public boolean oneEditAway(String first, String second) {
        int start1 = 0, end1 = first.length() - 1;
        int start2 = 0, end2 = second.length() - 1;
        while (start1 <= end1 && start2 <= end2) {
            if (first.charAt(start1) == second.charAt(start2)) {
                start1++;
                start2++;
                continue;
            }
            if (first.charAt(end1) == second.charAt(end2)) {
                end1--;
                end2--;
            } else
                break;
        }
        /*
        * 关键是这个傻逼好事者
        * 多写了个无用的条件，把我整蒙了半天
        * Math.abs(start1 - start2) <= 1
        *
        * 实际上，start1 和 start2 永远都是相等的！
        *
        * */
        return end1 - start1 + end2 - start2 <= 0 && Math.abs(end1 - end2) <= 1;
    }
}
